package org.example.leetcode;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:
 * @date: 2021/8/12 10:11
 */
public class LC63 {
    public static void main(String[] args) {

    }
    //fixme https://www.bilibili.com/video/BV12K41157r3?from=search&seid=10894439241651272214
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 带障碍物的 [0,0,0],[0,1,0],[0,0,0]  ，这个就代表 3*3，其中中间的一个1，代表障碍物


        int m=obstacleGrid.length;
        if (m==0) return 0; //fixme 为什么m=0 不 return n呢？ 因为有障碍物
        int n=obstacleGrid[0].length;
        if (n==0) return 0;
        int[][] dp=new int[m][n];
        //fixme 一般用到for循环，不用考虑空值
        for (int i = 0; i <m ; i++) {
            if (obstacleGrid[i][0]==1) break;//代表说有障碍物之后，后面不需要继续初始化了
            dp[i][0]=1;// fixme 初始化为 1
        }
        for (int i = 0; i <n ; i++) {
            if(obstacleGrid[0][i]==1) break;
            dp[0][i]=1; // fixme 初始化为 1
        }
        for(int i=1;i<m;i++){
            for (int j = 1; j <n ; j++) {
                if(obstacleGrid[i][j]==1) continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];//fixme 由于初始化是从0开始
    }
}
